#include "./binary-tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

BinaryTree createTreeByScanf(char tip[])
{
	printf("%s:", tip);
	char data = getchar();
	// 吸收回车
	getchar();
	// 根节点
	BTNode *node = NULL;
	// 连按两次回车表示结束当前节点创建
	if (data != 10)
	{
		node = (BTNode *)malloc(sizeof(BTNode));
		node->data = data;
		// 然后以同样的方式递归初始化其左右孩子
		char tipMessage[30];
		tipMessage[0] = data;
		tipMessage[1] = '\0';
		strcat(tipMessage, "的左孩子");
		node->left = createTreeByScanf(tipMessage);
		tipMessage[1] = '\0';
		strcat(tipMessage, "的右孩子");
		node->right = createTreeByScanf(tipMessage);
	}
	else
	{
		printf("成功设定叶子结点！\n");
	}
	// 最后返回根节点
	return node;
}

BinaryTree createTreeByArray(int i, int n, char datas[])
{
	// datas为层次遍历顺序，那么假设当前节点为datas[i]，则其左孩子为datas[2 * i + 1]，右孩子为datas[2 * i + 2]，i从0开始
	BTNode *node = NULL;
	// 0也视为空节点
	if (i > n - 1 || datas[i] == 0)
	{
		return node;
	}
	node = (BTNode *)malloc(sizeof(BTNode));
	node->data = datas[i];
	// 递归初始化左右孩子
	node->left = createTreeByArray(2 * i + 1, n, datas);
	node->right = createTreeByArray(2 * i + 2, n, datas);
	return node;
}

int indexOf(char target, char datas[])
{
	int i;
	for (i = 0; i < strlen(datas); i++)
	{
		if (datas[i] == target)
		{
			return i;
		}
	}
	return -1;
}

BinaryTree createTreeByPreOrderAndInOrder(char preOrder[], int preStart, int preEnd, char inOrder[], int inStart, int inEnd)
{
	BTNode *node = NULL;
	// 递归结束条件
	if (preStart > preEnd)
	{
		return NULL;
	}
	// 先初始化根节点
	node = (BTNode *)malloc(sizeof(BTNode));
	// 先序遍历中第一个就是根，因此把preOrder[preStart]赋给当根节点
	node->data = preOrder[preStart];
	// 找到根节点在中序遍历中的位置
	int inOrderIndex = indexOf(node->data, inOrder);
	// 若根节点位于中序遍历的inOrderIndex处，则可以推断出：
	// 左子树部分位于中序遍历的inStart到inOrderIndex - 1，左子树元素个数为inOrderIndex - inStart，因此左子树部分还位于先序遍历的preStart + 1到preStart + inOrderIndex - inStart
	// 右子树部分位于中序遍历的inOrderIndex + 1到inEnd，右子树元素个数为inEnd - inOrderIndex，因此右子树部分还位于先序遍历的preStart + inOrderIndex - inStart + 1到preEnd
	// 因此此处可以递归构建左右子树
	node->left = createTreeByPreOrderAndInOrder(preOrder, preStart + 1, preStart + inOrderIndex - inStart, inOrder, inStart, inOrderIndex - 1);
	node->right = createTreeByPreOrderAndInOrder(preOrder, preStart + inOrderIndex - inStart + 1, preEnd, inOrder, inOrderIndex + 1, inEnd);
	return node;
}

BinaryTree createTreeByPostOrderAndInOrder(char postOrder[], int postStart, int postEnd, char inOrder[], int inStart, int inEnd)
{
	BTNode *node = NULL;
	// 递归结束条件
	if (postStart > postEnd)
	{
		return NULL;
	}
	// 先初始化根节点
	node = (BTNode *)malloc(sizeof(BTNode));
	// 后续遍历的最后一个就是根，因此把postOrder[postEnd]赋给根
	node->data = postOrder[postEnd];
	// 找到根节点在中序遍历的位置
	int inOrderIndex = indexOf(node->data, inOrder);
	// 中序遍历中根节点位于inOrderIndex，因此可以推断出：
	// 左子树部分位于中序遍历的inStart到inOrderIndex - 1处，节点个数为inOrderIndex - inStart，因此左子树部分还位于后序遍历的postStart到postStart + inOrderIndex - inStart - 1
	// 右子树部分位于中序遍历的inOrderIndex + 1到inEnd处，节点个数为inEnd - inOrderIndex，因此右子树部分还位于后序遍历的postStart + inOrderIndex - inStart到postEnd - 1处
	// 因此此处可以递归构建左右子树
	node->left = createTreeByPostOrderAndInOrder(postOrder, postStart, postStart + inOrderIndex - inStart - 1, inOrder, inStart, inOrderIndex - 1);
	node->right = createTreeByPostOrderAndInOrder(postOrder, postStart + inOrderIndex - inStart, postEnd - 1, inOrder, inOrderIndex + 1, inEnd);
	return node;
}

BinaryTree treeToBinaryTree(Tree tree)
{
	BTNode *node = NULL;
	if (tree != NULL)
	{
		node = (BTNode *)malloc(sizeof(BTNode));
		node->data = tree->data;
		// 二叉树节点的左孩子是树节点的第一个孩子
		node->left = treeToBinaryTree(tree->firstChild);
		// 二叉树节点的右孩子是树节点的兄弟节点
		node->right = treeToBinaryTree(tree->nextBrother);
	}
	// 返回该二叉树节点
	return node;
}

void preorderTraverse(BinaryTree tree)
{
	if (tree != NULL)
	{
		// 先访问根节点，然后递归访问左右孩子
		printf("%c ", tree->data);
		preorderTraverse(tree->left);
		preorderTraverse(tree->right);
	}
}

void preorderTraverseNonRecursion(BinaryTree tree)
{
	// 根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子
	// 即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树，当访问完成其左子树时，再访问它的右子树
	BTNode *stack[100], *pointer = tree;
	int top = 0;
	// 当指针为空且栈为空，说明遍历完成
	while (pointer != NULL || top != 0)
	{
		while (pointer != NULL)
		{
			// 先访问根节点
			printf("%c ", pointer->data);
			// 根节点入栈
			stack[top++] = pointer;
			// 下一步访问左孩子，作为根节点访问
			pointer = pointer->left;
		}
		// 到这里，没有左孩子了，那就往回退一个，访问右孩子，然后继续访问其左孩子
		if (top != 0)
		{
			// 出栈回退一个
			pointer = stack[--top];
			// 指向右孩子，作为根节点访问
			pointer = pointer->right;
		}
	}
	printf("\n");
}

void inorderTraverse(BinaryTree tree)
{
	if (tree != NULL)
	{
		// 先递归访问左孩子，然后访问根，最后递归访问右孩子
		inorderTraverse(tree->left);
		printf("%c ", tree->data);
		inorderTraverse(tree->right);
	}
}

void inorderTraverseNonRecursion(BinaryTree tree)
{
	// 根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树
	BTNode *stack[100], *pointer = tree;
	int top = 0;
	// 当指针为空且栈为空，说明遍历完成
	while (pointer != NULL || top != 0)
	{
		// 先把根节点存起来，然后找左孩子，直到为空再拿出来访问
		while (pointer != NULL)
		{
			stack[top++] = pointer;
			pointer = pointer->left;
		}
		// 到这里左孩子为空了，退栈一个并访问，并将指针置于其右子树，回到上述循环以相同规则继续
		if (top != 0)
		{
			pointer = stack[--top];
			printf("%c ", pointer->data);
			pointer = pointer->right;
		}
	}
	printf("\n");
}

void postorderTraverse(BinaryTree tree)
{
	if (tree != NULL)
	{
		// 先递归访问左右孩子，然后访问根
		postorderTraverse(tree->left);
		postorderTraverse(tree->right);
		printf("%c ", tree->data);
	}
}

void postorderTraverseNonRecursion(BinaryTree tree)
{
	if (tree == NULL)
	{
		return;
	}
	// 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈，然后：
	// 1. 如果P不存在左孩子和右孩子，则可以直接访问它
	// 2. 如果P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点
	// 3. 若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问
	// 栈、当前指向节点与前一个节点
	BTNode *stack[100], *pointer, *prior;
	int top = 0;
	// 先开始根节点入栈
	stack[top++] = tree;
	while (top != 0)
	{
		// 记录当前节点为栈顶
		pointer = stack[top - 1];
		// 判断是否可以直接访问的节点
		if ((pointer->left == NULL && pointer->right == NULL) || (prior != NULL && (prior == pointer->left || prior == pointer->right)))
		{
			// 访问并出栈
			printf("%c ", pointer->data);
			top--;
			// 记录为上一节点然后往下走
			prior = pointer;
		}
		else
		{
			// 依次把右孩子左孩子入栈
			if (pointer->right != NULL)
			{
				stack[top++] = pointer->right;
			}
			if (pointer->left != NULL)
			{
				stack[top++] = pointer->left;
			}
		}
	}
	printf("\n");
}

void hierarchicalTraverse(BinaryTree tree)
{
	if (tree == NULL)
	{
		return;
	}
	// 使用一个存放辅助循环队列来进行层次遍历
	// 队列容量，头尾下标指针
	int queueMax = 100, rear = 0, front = 0;
	// 队列以及出队时的临时节点
	BTNode *queue[queueMax], *temp;
	// 根节点先入队
	queue[rear] = tree;
	rear = (rear + 1) % queueMax;
	// 队列不为空时，将其中的节点出队并打印，并把该节点的左右孩子入队
	while (rear != front)
	{
		temp = queue[front];
		front = (front + 1) % queueMax;
		printf("%c ", temp->data);
		// 左右孩子入队
		if (temp->left != NULL)
		{
			queue[rear] = temp->left;
			rear = (rear + 1) % queueMax;
		}
		if (temp->right != NULL)
		{
			queue[rear] = temp->right;
			rear = (rear + 1) % queueMax;
		}
	}
}

int nodeCount(BinaryTree tree)
{
	int leftCount, rightCount;
	if (tree == NULL)
	{
		return 0;
	}
	// 递归计算左子树节点数
	leftCount = nodeCount(tree->left);
	// 递归计算右子树节点数
	rightCount = nodeCount(tree->right);
	// 左右子树结点数加上自己则为总的节点数
	return leftCount + rightCount + 1;
}

int leafCount(BinaryTree tree)
{
	int leftLeafCount, rightLeafCount;
	if (tree == NULL)
	{
		return 0;
	}
	// 如果当前节点为叶子节点，返回1，供下面递归相加
	if (tree->left == NULL && tree->right == NULL)
	{
		return 1;
	}
	// 递归计算左右子树的叶子节点数
	leftLeafCount = leafCount(tree->left);
	rightLeafCount = leafCount(tree->right);
	return leftLeafCount + rightLeafCount;
}

int notLeafCount(BinaryTree tree)
{
	// 若当前结点为NULL，或者当前结点为叶子结点，返回0
	if (tree == NULL || (tree->left == NULL && tree->right == NULL))
	{
		return 0;
	}
	// 否则，递归计算左右子树
	int left = notLeafCount(tree->left);
	int right = notLeafCount(tree->right);
	return left + right + 1;
}

int singleBranchCount(BinaryTree tree)
{
	int leftCount, rightCount;
	if (tree == NULL)
	{
		return 0;
	}
	// 只有一个孩子节点的视为单分支节点
	if ((tree->left == NULL && tree->right != NULL) || (tree->left != NULL && tree->right == NULL))
	{
		leftCount = singleBranchCount(tree->left);
		rightCount = singleBranchCount(tree->right);
		return leftCount + rightCount + 1;
	}
	// 否则仅递归统计
	leftCount = singleBranchCount(tree->left);
	rightCount = singleBranchCount(tree->right);
	return leftCount + rightCount;
}

int doubleBranchCount(BinaryTree tree)
{
	int leftCount, rightCount;
	if (tree == NULL)
	{
		return 0;
	}
	// 有两个孩子节点的视为双分支节点
	if (tree->left != NULL && tree->right != NULL)
	{
		leftCount = doubleBranchCount(tree->left);
		rightCount = doubleBranchCount(tree->right);
		return leftCount + rightCount + 1;
	}
	// 否则仅递归统计
	leftCount = doubleBranchCount(tree->left);
	rightCount = doubleBranchCount(tree->right);
	return leftCount + rightCount;
}

int childCount(BTNode *node)
{
	int leftCount = 0, rightCount = 0;
	if (node == NULL)
	{
		return 0;
	}
	if (node->left != NULL)
	{
		leftCount = childCount(node->left) + 1;
	}
	if (node->right != NULL)
	{
		rightCount = childCount(node->right) + 1;
	}
	return leftCount + rightCount;
}

int treeHeight(BinaryTree tree)
{
	int leftHeight, rightHeight;
	if (tree == NULL)
	{
		return 0;
	}
	leftHeight = treeHeight(tree->left);
	rightHeight = treeHeight(tree->right);
	// 取左右子树最大值并加一
	return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}

int treeWidth(BinaryTree tree)
{
	// 使用队列辅助层次遍历实现
	if (tree == NULL)
	{
		return 0;
	}
	// 分别表示最大宽度，队列容量，队头和队尾指针下标，当前这一层的节点数记录
	int maxWidth = 0, queueMax = 100, rear = 0, front = 0, currentFloorSize;
	// 存放节点的循环队列，出队时临时节点
	BTNode *queue[1000], *temp;
	// 根节点先入队
	queue[rear] = tree;
	rear = (rear + 1) % queueMax;
	// 当队列不为空，每一趟会将一层节点出队并将它们的下一层入队
	while (rear != front)
	{
		// 这一趟出队之前先记录队列中元素个数，队列中元素个数即为这一层的节点数
		currentFloorSize = (rear - front + queueMax) % queueMax;
		maxWidth = (currentFloorSize > maxWidth) ? currentFloorSize : maxWidth;
		// 然后当前层全部出队，出队时使每个出队元素的子节点入队
		while (currentFloorSize > 0)
		{
			temp = queue[front];
			front = (front + 1) % queueMax;
			currentFloorSize--;
			// 出队的节点的左右子树入队
			if (temp->left != NULL)
			{
				queue[rear] = temp->left;
				rear = (rear + 1) % queueMax;
			}
			if (temp->right != NULL)
			{
				queue[rear] = temp->right;
				rear = (rear + 1) % queueMax;
			}
		}
	}
	return maxWidth;
}

int normalTreeHeight(Tree tree)
{
	int childHeight, brotherHeight;
	if (tree == NULL)
	{
		return 0;
	}
	childHeight = normalTreeHeight(tree->firstChild);
	brotherHeight = normalTreeHeight(tree->nextBrother);
	return (childHeight + 1 > brotherHeight) ? childHeight + 1 : brotherHeight;
}

BTNode *searchSortTree(BinaryTree tree, BTNode *parent, int data)
{
	// 当前节点为空说明找不到对应节点，返回查找路径上的最后一个节点
	if (tree == NULL)
	{
		return parent;
	}
	if (tree->data == data)
	{
		return tree;
	}
	if (data > (int)tree->data)
	{
		return searchSortTree(tree->right, tree, data);
	}
	else
	{
		return searchSortTree(tree->left, tree, data);
	}
}

void insertSortTree(BinaryTree tree, int data)
{
	BTNode *getNode = searchSortTree(tree, NULL, data);
	// 如果插入的值已经存在于排序树中，则不进行任何操作
	if ((int)getNode->data == data)
	{
		return;
	}
	// 创建节点
	BTNode *node = (BTNode *)malloc(sizeof(BTNode));
	node->data = data;
	node->left = node->right = NULL;
	// 若整个二叉树为空，则直接将插入结点变为根节点
	if (tree == NULL)
	{
		tree = node;
		return;
	}
	// 否则比较大小判断作为左孩子还是右孩子
	if (data > (int)getNode->data)
	{
		getNode->right = node;
	}
	else
	{
		getNode->left = node;
	}
}

BinaryTree createSortTree(int nodes[], int n)
{
	int i;
	BinaryTree root = (BTNode *)malloc(sizeof(BTNode));
	root->data = nodes[0];
	root->left = root->right = NULL;
	for (i = 1; i < n; i++)
	{
		insertSortTree(root, nodes[i]);
	}
	return root;
}

int former = -1;
int flag = 1;
int isSortTree(BinaryTree tree)
{
	// 对二叉树进行中序遍历，如果节点值是从小到大的则为二叉排序树，否则不是
	if (tree != NULL)
	{
		isSortTree(tree->left);
		if (former > (int)tree->data)
		{
			flag = 0;
		}
		former = tree->data;
		isSortTree(tree->right);
	}
	return flag;
}

int isComplete(BinaryTree tree)
{
	// 使用层次遍历的方式，每次把一层节点包括空节点都加入队列，如果出队列时遇到空节点，且空节点后面有非空节点，则说明不是完全二叉树
	// 空树也是完全二叉树
	if (tree == NULL)
	{
		return 1;
	}
	// 队列头尾下标指针，队列容量
	int rear, front, maxSize = 100;
	// 初始化循环队列，出队时临时节点
	BTNode *queue[maxSize], *temp;
	// 根节点先进入
	queue[rear] = tree;
	rear = (rear + 1) % maxSize;
	while (rear != front)
	{
		// 出队时，检查当前元素是否为空
		temp = queue[front];
		front = (front + 1) % maxSize;
		// 非空则左右节点入队
		if (temp != NULL)
		{
			queue[rear] = temp->left;
			rear = (rear + 1) % maxSize;
			queue[rear] = temp->right;
			rear = (rear + 1) % maxSize;
		}
		else
		{
			// 否则出队一个元素，若为非空说明不是完全二叉树
			temp = queue[front];
			front = (front + 1) % maxSize;
			if (temp != NULL)
			{
				return 0;
			}
		}
	}
	return 1;
}

int isBalance(BinaryTree tree)
{
	// 计算左右子树高度，高度差大于1则不是平衡二叉树
	int leftHeight = treeHeight(tree->left);
	int rightHeight = treeHeight(tree->right);
	if (abs(leftHeight - rightHeight) > 1)
	{
		return 0;
	}
	return 1;
}

BTNode *getNode(BinaryTree tree, char data)
{
	// 层次遍历法查找
	int max = 100, rear = 0, front = 0;
	BTNode *temp, *queue[max];
	// 判断根节点
	if (tree->data == data)
	{
		return tree;
	}
	// 否则根节点入队
	queue[rear] = tree;
	rear = (rear + 1) % max;
	// 依次判断左右子树，不相等则入队等待其子节点判断
	while (front != rear)
	{
		// 出队一个
		temp = queue[front];
		front = (front + 1) % max;
		if (temp->left != NULL)
		{
			if (temp->left->data == data)
			{
				return temp->left;
			}
			queue[rear] = temp->left;
			rear = (rear + 1) % max;
		}
		if (temp->right != NULL)
		{
			if (temp->right->data == data)
			{
				return temp->right;
			}
			queue[rear] = temp->right;
			rear = (rear + 1) % max;
		}
	}
	return NULL;
}

int treeEquals(BinaryTree tree1, BinaryTree tree2)
{
	// 递归结束条件：两者都为NULL时
	if (tree1 == NULL && tree2 == NULL)
	{
		return 1;
	}
	// 比较当前节点，若不一致，即其中一个为空或者两者值不一样，说明两树中有不同节点，不一样
	if ((tree1 == NULL && tree2 != NULL) || (tree1 != NULL && tree2 == NULL) || tree1->data != tree2->data)
	{
		return 0;
	}
	// 否则，继续递归比较左右孩子
	return treeEquals(tree1->left, tree2->left) && treeEquals(tree1->right, tree2->right);
}

int isSubTree(BinaryTree subTree, BinaryTree tree)
{
	// 先找到tree2的根节点对应的tree1中的
	BTNode *subRootTree = getNode(tree, subTree->data);
	if (subRootTree == NULL)
	{
		return 0;
	}
	return treeEquals(subTree, subRootTree);
}